/*
Given a 2-D MxN matrix having each value as difficulty for the block. A frog is starting from a point Matrix[0][0] and will have to reach Matrix[M-1][N-1]. It can jump any step in one go [ 1, 2, ..... M-1] horizontally OR [ 1,2,3,.... N-1] vertically
Each difficulty value is positive. Write code to give path trace for frog.
Two structure to use -

struct node
{
int x;
int y;
struct node *next;
};

struct path
{
int difficulty;
struct node *pathlink;
}

Ex matrix - 4X4 matrix

7 9 2 11
13 23 1 3
14 11 20 6
22 44 3 15

Minimum difficulty = 7 (a[0][0])+ 2(a[0][2]) +3(a[3][2])+15(a[3][3]) = 27
Path trace will have = 7->2->3->15


*/
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;

//dynamic programming
int findDiff(int diff[][4], int w, int h)
{
    vector<vector<int> > mat(w, vector<int>(h, 0));
   /* for (int i = 0; i < w; i++) mat[0][i] = diff[0][i];
    for (int j = 0; j < h; j++) mat[j][0] = diff[j][0]; */
    mat[0][0] = diff[0][0];

    for (int i = 0; i < w; i++) {
	for (int j = 0; j < h; j++) {
	    if (i == 0 && j == 0) continue;
	    int minDis = 1000000;
	    for (int k = 0; k < i; k++) 
		minDis = min(mat[k][j] + diff[i][j], minDis);
	    for (int l = 0; l < j; l++)
		minDis = min(mat[i][l] + diff[i][j], minDis);
	    mat[i][j] = minDis;
	}
    }
    for (int i = 0; i < w; i++) {
	for (int j = 0; j < h; j++)
	    cout << mat[i][j] << " ";
	cout << endl;
    }
    return mat[w-1][h-1];
}


int main(int argc, char **argv)
{
    int dif[][4] = {{7, 9, 2, 11},
		    {13, 23, 1, 3},
		    {14, 11, 20, 6},
		    {22, 44, 3, 15}};
    cout << findDiff(dif, 4, 4) << endl;
}
